package com.cn.algorithm.one.heap;

import java.util.HashMap;
import java.util.Map;

public class Trie<V> {

    Node<V> root;

    int size;


    public int size() {
        return size;
    }

    public boolean siEmpty() {
        return size == 0;
    }

    public void clear() {
        root = null;
        size = 0;
    }

    public V get(String key) {
        Node<V> node = node(key);
        return node != null && node.word ? node.value : null;
    }

    public boolean contains(String key) {
        Node<V> node = node(key);
        return node != null && node.word;
    }

    public boolean startWith(String key) {
        return node(key) != null;
    }

    public V add(String key, V value) {
        if (root == null) {
            root = new Node<>(null);
        }
        Node<V> node = root;
        for (int i = 0; i < key.length(); i++) {
            if (node.children == null) {
                node.children = new HashMap<>();
            }
            char c = key.charAt(i);
            if (node.children.get(c) == null) {
                Node<V> childNode = new Node<>(node);
                childNode.character = c;
                node.children.put(c, childNode);
            }
            node = node.children.get(c);
        }
        if (node.word) {
            V oldValue = node.value;
            node.value = value;
            return oldValue;
        }
        node.word = true;
        node.value = value;
        size++;
        return null;
    }

    public V remove(String key) {
        Node<V> node = node(key);
        if (node == null || !node.word) {
            return null;
        }
        size--;
        V oldValue = node.value;
        if (node.children != null && !node.children.isEmpty()) {//当前节点下面还有节点
            node.value = null;
            node.word = false;
            return oldValue;
        }
        Node<V> parent = null;
        while ((parent = node.parent) != null) {
            parent.children.remove(node.character);
            if (parent.word || !parent.children.isEmpty()) {
                break;
            }
            node = parent;
        }
        return oldValue;
    }

    public Node<V> node(String key) {
        Node<V> node = root;
        for (int i = 0; i < key.length(); i++) {
            char c = key.charAt(i);
            if (node == null || node.children == null || node.children.get(c) == null) {
                return null;
            }
            node = node.children.get(c);
        }
        return node;
    }


    public static class Node<V> {

        Node<V> parent;

        Character character;
        Map<Character, Node<V>> children;

        boolean word;

        V value;

        public Node(Node<V> parent) {
            this.parent = parent;
        }
    }


    public static void main(String[] args) {
        Trie<Integer> trie = new Trie<>();
        trie.add("cat", 1);
        trie.add("dog", 2);
        trie.add("catalog", 3);
        trie.add("cast", 4);
        trie.add("小码哥", 5);
        System.out.println(trie.size());
        System.out.println(trie.get("dog"));
        System.out.println(trie.remove("cast"));
        System.out.println(trie.startWith("ca"));
        System.out.println(trie.size);

    }
}
